Allocation optimale des ressources pour les applications et services de grille de calcul

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Optimisation des horaires des agents et du routage des appels dans les centres d’appels

Nous étudions la gestion de centres d'appels multi-compétences, ayant plusieurs types d'appels et groupes d'agents. Un centre d'appels est un système de files d'attente très complexe, où il faut généralement utiliser un simulateur pour évaluer ses performances. Tout d'abord, nous développons un simulateur de centres d'appels basé sur la simulation d'une chaîne de Markov en temps continu (CMTC), qui est plus rapide que la simulation conventionnelle par événements discrets. À l'aide d'une méthode d'uniformisation de la CMTC, le simulateur simule la chaîne de Markov en temps discret imbriquée de la CMTC. Nous proposons des stratégies pour utiliser efficacement ce simulateur dans l'optimisation de l'affectation des agents. En particulier, nous étudions l'utilisation des variables aléatoires communes. Deuxièmement, nous optimisons les horaires des agents sur plusieurs périodes en proposant un algorithme basé sur des coupes de sous-gradients et la simulation. Ce problème est généralement trop grand pour être optimisé par la programmation en nombres entiers. Alors, nous relaxons l'intégralité des variables et nous proposons des méthodes pour arrondir les solutions. Nous présentons une recherche locale pour améliorer la solution finale. Ensuite, nous étudions l'optimisation du routage des appels aux agents. Nous proposons une nouvelle politique de routage basé sur des poids, les temps d'attente des appels, et les temps d'inoccupation des agents ou le nombre d'agents libres. Nous développons un algorithme génétique modifié pour optimiser les paramètres de routage. Au lieu d'effectuer des mutations ou des croisements, cet algorithme optimise les paramètres des lois de probabilité qui génèrent la population de solutions. Par la suite, nous développons un algorithme d'affectation des agents basé sur l'agrégation, la théorie des files d'attente et la probabilité de délai. Cet algorithme heuristique est rapide, car il n'emploie pas la simulation. La contrainte sur le niveau de service est convertie en une contrainte sur la probabilité de délai. Par après, nous proposons une variante d'un modèle de CMTC basé sur le temps d'attente du client à la tête de la file. Et finalement, nous présentons une extension d'un algorithme de coupe pour l'optimisation stochastique avec recours de l'affectation des agents dans un centre d'appels multi-compétences.

Staffing Optimization with Chance Constraints in Call Centers

Les centres d’appels sont des éléments clés de presque n’importe quelle grande organisation. Le problème de gestion du travail a reçu beaucoup d’attention dans la littérature. Une formulation typique se base sur des mesures de performance sur un horizon infini, et le problème d’affectation d’agents est habituellement résolu en combinant des méthodes d’optimisation et de simulation. Dans cette thèse, nous considérons un problème d’affection d’agents pour des centres d’appels soumis a des contraintes en probabilité. Nous introduisons une formulation qui exige que les contraintes de qualité de service (QoS) soient satisfaites avec une forte probabilité, et définissons une approximation de ce problème par moyenne échantillonnale dans un cadre de compétences multiples. Nous établissons la convergence de la solution du problème approximatif vers celle du problème initial quand la taille de l’échantillon croit. Pour le cas particulier où tous les agents ont toutes les compétences (un seul groupe d’agents), nous concevons trois méthodes d’optimisation basées sur la simulation pour le problème de moyenne échantillonnale. Étant donné un niveau initial de personnel, nous augmentons le nombre d’agents pour les périodes où les contraintes sont violées, et nous diminuons le nombre d’agents pour les périodes telles que les contraintes soient toujours satisfaites après cette réduction. Des expériences numériques sont menées sur plusieurs modèles de centre d’appels à faible occupation, au cours desquelles les algorithmes donnent de bonnes solutions, i.e. la plupart des contraintes en probabilité sont satisfaites, et nous ne pouvons pas réduire le personnel dans une période donnée sont introduire de violation de contraintes. Un avantage de ces algorithmes, par rapport à d’autres méthodes, est la facilité d’implémentation.

Modèle de confiance et ontologie probabiliste pilotés par réseaux bayésiens pour la gestion des accords de services dans l’environnement de services infonuagiques

L’infonuage est un nouveau paradigme de services informatiques disponibles à la demande qui a connu une croissance fulgurante au cours de ces dix dernières années. Le fournisseur du modèle de déploiement public des services infonuagiques décrit le service à fournir, le prix, les pénalités en cas de violation des spécifications à travers un document. Ce document s’appelle le contrat de niveau de service (SLA). La signature de ce contrat par le client et le fournisseur scelle la garantie de la qualité de service à recevoir. Ceci impose au fournisseur de gérer efficacement ses ressources afin de respecter ses engagements. Malheureusement, la violation des spécifications du SLA se révèle courante, généralement en raison de l’incertitude sur le comportement du client qui peut produire un nombre variable de requêtes vu que les ressources lui semblent illimitées. Ce comportement peut, dans un premier temps, avoir un impact direct sur la disponibilité du service. Dans un second temps, des violations à répétition risquent d'influer sur le niveau de confiance du fournisseur et sur sa réputation à respecter ses engagements. Pour faire face à ces problèmes, nous avons proposé un cadre d’applications piloté par réseau bayésien qui permet, premièrement, de classifier les fournisseurs dans un répertoire en fonction de leur niveau de confiance. Celui-ci peut être géré par une entité tierce. Un client va choisir un fournisseur dans ce répertoire avant de commencer à négocier le SLA. Deuxièmement, nous avons développé une ontologie probabiliste basée sur un réseau bayésien à entités multiples pouvant tenir compte de l’incertitude et anticiper les violations par inférence. Cette ontologie permet de faire des prédictions afin de prévenir des violations en se basant sur les données historiques comme base de connaissances. Les résultats obtenus montrent l’efficacité de l’ontologie probabiliste pour la prédiction de violation dans l’ensemble des paramètres SLA appliqués dans un environnement infonuagique.

Scheduled service network design for integrated planning of rail freight transportation

Cette thèse étudie une approche intégrant la gestion de l’horaire et la conception de réseaux de services pour le transport ferroviaire de marchandises. Le transport par rail s’articule autour d’une structure à deux niveaux de consolidation où l’affectation des wagons aux blocs ainsi que des blocs aux services représentent des décisions qui complexifient grandement la gestion des opérations. Dans cette thèse, les deux processus de consolidation ainsi que l’horaire d’exploitation sont étudiés simultanément. La résolution de ce problème permet d’identifier un plan d’exploitation rentable comprenant les politiques de blocage, le routage et l’horaire des trains, de même que l’habillage ainsi que l’affectation du traffic. Afin de décrire les différentes activités ferroviaires au niveau tactique, nous étendons le réseau physique et construisons une structure de réseau espace-temps comprenant trois couches dans lequel la dimension liée au temps prend en considération les impacts temporels sur les opérations. De plus, les opérations relatives aux trains, blocs et wagons sont décrites par différentes couches. Sur la base de cette structure de réseau, nous modélisons ce problème de planification ferroviaire comme un problème de conception de réseaux de services. Le modèle proposé se formule comme un programme mathématique en variables mixtes. Ce dernie r s’avère très difficile à résoudre en raison de la grande taille des instances traitées et de sa complexité intrinsèque. Trois versions sont étudiées : le modèle simplifié (comprenant des services directs uniquement), le modèle complet (comprenant des services directs et multi-arrêts), ainsi qu’un modèle complet à très grande échelle. Plusieurs heuristiques sont développées afin d’obtenir de bonnes solutions en des temps de calcul raisonnables. Premièrement, un cas particulier avec services directs est analysé. En considérant une cara ctéristique spécifique du problème de conception de réseaux de services directs nous développons un nouvel algorithme de recherche avec tabous. Un voisinage par cycles est privilégié à cet effet. Celui-ci est basé sur la distribution du flot circulant sur les blocs selon les cycles issus du réseau résiduel. Un algorithme basé sur l’ajustement de pente est développé pour le modèle complet, et nous proposons une nouvelle méthode, appelée recherche ellipsoidale, permettant d’améliorer davantage la qualité de la solution. La recherche ellipsoidale combine les bonnes solutions admissibles générées par l’algorithme d’ajustement de pente, et regroupe les caractéristiques des bonnes solutions afin de créer un problème élite qui est résolu de facon exacte à l’aide d’un logiciel commercial. L’heuristique tire donc avantage de la vitesse de convergence de l’algorithme d’ajustement de pente et de la qualité de solution de la recherche ellipsoidale. Les tests numériques illustrent l’efficacité de l’heuristique proposée. En outre, l’algorithme représente une alternative intéressante afin de résoudre le problème simplifié. Enfin, nous étudions le modèle complet à très grande échelle. Une heuristique hybride est développée en intégrant les idées de l’algorithme précédemment décrit et la génération de colonnes. Nous proposons une nouvelle procédure d’ajustement de pente où, par rapport à l’ancienne, seule l’approximation des couts liés aux services est considérée. La nouvelle approche d’ajustement de pente sépare ainsi les décisions associées aux blocs et aux services afin de fournir une décomposition naturelle du problème. Les résultats numériques obtenus montrent que l’algorithme est en mesure d’identifier des solutions de qualité dans un contexte visant la résolution d’instances réelles.

Routage adaptatif et qualité de service dans les réseaux optiques à commutation de rafales

Les réseaux optiques à commutation de rafales (OBS) sont des candidats pour jouer un rôle important dans le cadre des réseaux optiques de nouvelle génération. Dans cette thèse, nous nous intéressons au routage adaptatif et au provisionnement de la qualité de service dans ce type de réseaux. Dans une première partie de la thèse, nous nous intéressons à la capacité du routage multi-chemins et du routage alternatif (par déflection) à améliorer les performances des réseaux OBS, pro-activement pour le premier et ré-activement pour le second. Dans ce contexte, nous proposons une approche basée sur l’apprentissage par renforcement où des agents placés dans tous les nœuds du réseau coopèrent pour apprendre, continuellement, les chemins du routage et les chemins alternatifs optimaux selon l’état actuel du réseau. Les résultats numériques montrent que cette approche améliore les performances des réseaux OBS comparativement aux solutions proposées dans la littérature. Dans la deuxième partie de cette thèse, nous nous intéressons au provisionnement absolu de la qualité de service où les performances pire-cas des classes de trafic de priorité élevée sont garanties quantitativement. Plus spécifiquement, notre objectif est de garantir la transmission sans pertes des rafales de priorité élevée à l’intérieur du réseau OBS tout en préservant le multiplexage statistique et l’utilisation efficace des ressources qui caractérisent les réseaux OBS. Aussi, nous considérons l’amélioration des performances du trafic best effort. Ainsi, nous proposons deux approches : une approche basée sur les nœuds et une approche basée sur les chemins. Dans l’approche basée sur les nœuds, un ensemble de longueurs d’onde est assigné à chaque nœud du bord du réseau OBS pour qu’il puisse envoyer son trafic garanti. Cette assignation prend en considération les distances physiques entre les nœuds du bord. En outre, nous proposons un algorithme de sélection des longueurs d’onde pour améliorer les performances des rafales best effort. Dans l’approche basée sur les chemins, le provisionnement absolu de la qualité de service est fourni au niveau des chemins entre les nœuds du bord du réseau OBS. À cette fin, nous proposons une approche de routage et d’assignation des longueurs d’onde qui a pour but la réduction du nombre requis de longueurs d’onde pour établir des chemins sans contentions. Néanmoins, si cet objectif ne peut pas être atteint à cause du nombre limité de longueurs d’onde, nous proposons de synchroniser les chemins en conflit sans le besoin pour des équipements additionnels. Là aussi, nous proposons un algorithme de sélection des longueurs d’onde pour les rafales best effort. Les résultats numériques montrent que l’approche basée sur les nœuds et l’approche basée sur les chemins fournissent le provisionnement absolu de la qualité de service pour le trafic garanti et améliorent les performances du trafic best effort. En outre, quand le nombre de longueurs d’ondes est suffisant, l’approche basée sur les chemins peut accommoder plus de trafic garanti et améliorer les performances du trafic best effort par rapport à l’approche basée sur les nœuds.

Le Service à la famille de l'organisme Dans la rue : points de vue et expériences de jeunes qui y ont fait appel

Malgré l’intérêt accru du public et de la recherche durant les deux dernières décennies pour le phénomène des jeunes de la rue, certains aspects de leurs réalités sont encore peu examinés et mal connus. L’un de ces aspects concerne la parentalité. Pour mieux comprendre les besoins des jeunes en situation de rue qui sont parents ou en voie de l’être et comprendre dans quelle mesure un service s’adressant spécifiquement à eux arrive à y répondre, cette étude a cherché à décrire et comprendre l’expérience d’utilisation du Service à la famille de l’organisme Dans la rue, telle que vécue par des jeunes qui s’y sont adressés. Plus précisément, les objectifs étaient de : situer le Service à la famille dans la démarche de recherche d’aide des jeunes; comprendre ce qui amène un jeune à utiliser le Service à la famille et les activités qui y sont offertes; décrire l’expérience d’utilisation du service; connaître la perception qu’en ont les jeunes; et estimer leur appréciation du service. Pour ce faire, des entrevues semi-dirigées par téléphone ont eu lieu avec neuf jeunes ayant eu un suivi au Service à la famille, au cours desquelles certains thèmes ont été explorés : la recherche d’aide en lien avec la situation parentale, l’expérience d’utilisation des services et des activités du Service à la famille, le portrait de celui-ci, et la satisfaction à son égard. Au moment de l’entrevue, tous les jeunes étaient parents d’au moins un enfant et la majorité d’entre eux avait fait appel au Service à la famille la première fois durant la grossesse pour de l’aide sous diverses formes en rapport à celle-ci. Des besoins de divers ordres ont amené les jeunes à faire appel au Service à la famille. Ceux-ci pouvaient être comblés, mais pas nécessairement toujours, par le biais des rencontres avec les intervenantes du Service à la famille et par la participation aux activités de groupe offertes par la ressource et, par ailleurs, pouvaient concorder avec les objectifs d’intervention explicites du service. Dans l’ensemble, les entrevues suggèrent que les jeunes perçoivent le Service à la famille et, plus précisément, les intervenantes qui y travaillent, d’un œil favorable. Les interviewés formulent en effet une appréciation positive sur un bon nombre d’éléments se rapportant à leur expérience d’utilisation de la ressource. Des jeunes perçoivent néanmoins des limites dans la capacité du Service à la famille à fournir l’aide attendue, notamment des restrictions budgétaires et une surcharge de travail des intervenantes liée à une forte demande de services. Même si les jeunes n’ont pas nécessairement demandé de l’aide de la ressource dans l’optique de prévenir la violence familiale et la négligence, mandat premier du Service à la famille, une bonne part d’entre eux reconnaissent avoir reçu de l’aide utile à cet égard de la part des intervenantes, notamment lorsqu’ils ont rapporté avoir vécu des relations amoureuses teintées de violence conjugale. Ils reconnaissent également différentes façons par le biais desquelles les intervenantes les auraient encouragés à être bien et à prendre soin d’eux-mêmes afin de pouvoir bien s’occuper de leur(s) enfant(s). Tous les jeunes interviewés ont exprimé une satisfaction à l’égard du suivi reçu au Service à la famille et ils ont affirmé qu’ils le recommanderaient à d’autres personnes. L’approche d’intervention préconisée par la ressource est considérée comme un point fort dans la réponse aux besoins des jeunes. Cette approche aurait permis aux jeunes devenus parents d’être aidés en fonction de ce dont ils avaient besoin à un moment précis. L’un des aspects de l’utilisation du service qui gagneraient à être améliorés, aux yeux des jeunes, est l’accessibilité; l’aide dont les interviewés considéraient avoir besoin n’ayant pas toujours été à leur disposition alors qu’ils l’avaient demandée. Devant la perception d’un manque de disponibilité des intervenantes, des jeunes proposent des pistes d’amélioration qui permettraient à l’aide dispensée par le Service à la famille d’être plus accessible aux jeunes quand ils considèrent en avoir besoin.

How to build a bioinformatics service in a year

Introduction: Biomedical scientists need to choose among hundreds of publicly available bioinformatics applications, tools, and databases. Librarian challenges include raising awareness to valuable resources, as well as providing support in finding and evaluating specific resources. Our objective is to implement an education program in bioinformatics similar to those offered in other North American academic libraries. Description: Our initial target clientele included four research departments of the Faculty of Medicine at Universite´ de Montréal. In January 2010, I attended two departmental meetings and interviewed a few stakeholders in order to propose a basic bioinformatics service: one-to-one consultations and a workshop on NCBI databases. The response was favourable. The workshop was thus offered once a month during the Winter and Fall semesters, and participants were invited to evaluate the workshop via an online survey. In addition, a bioinformatics subject guide was launched on the library’s website in December 2010. Outcomes: One hundred and two participants attended one of the nine NCBI workshops offered in 2010; most were graduate students (74%). The survey’s response rate was 54%. A majority of respondents thought that the bioinformatics resources featured in the workshop were relevant (95%) and that the difficulty level of exercises was appropriate (84%). Respondents also thought that their future information searches would be more efficient (93%) and that the workshop should be integrated in a course (78%). Furthermore, five bioinformatics-related reference questions were answered and two one-to-one consultations with students were performed. Discussion: The success of our bioinformatics service is growing. Future directions include extending the service to other biomedical departments, integrating the workshop in an undergraduate course, promoting the subject guide to other francophone universities, and creating a bioinformatics blog that would feature specific databases, news, and library resources.

Décrire quantitativement les interventions téléphoniques des infirmières au service Info-Santé selon le niveau de compétence novice - compétent - expert

Ce mémoire est un des segments d'une recherche de plus grande envergure sur le service Info-Santé, et qui se déroule au Centre de Santé et de Services sociaux de Laval.

Les pratiques d’intervention policières auprès des personnes en crise ou atteintes de troubles mentaux : le cas des agents de réponse en intervention de crise du Service de police de la Ville de Montréal

Cette recherche porte sur les pratiques d’intervention des agents de réponse en intervention de crise (RIC), de leur partenaire fixe et des agents en attente de la formation du Service de police de la Ville de Montréal (SPVM) auprès des personnes en crise ou atteintes de troubles mentaux. Les agents RIC sont des patrouilleurs de première ligne qui ont reçu une formation complète sur les principes d’intervention en contexte de crise ou de santé mentale. Ce modèle de réponse spécialisée est une solution proactive qui a pour but d’améliorer l’action policière en situation de crise et de veiller à une meilleure prise en charge de ces personnes par les ressources institutionnelles. La désinstitutionnalisation des soins et des services psychiatriques a eu pour effet une augmentation du nombre de personnes atteintes de troubles mentaux dans la communauté. Par conséquent, cet accroissement a engendré des rapports plus fréquents entre les services policiers et cette clientèle. Les interventions en contexte de crise ou de santé mentale sont particulières et complexes, de même qu’elles requièrent un niveau supérieur de compréhension des crises humaines. Les autorités policières ont admis que ces interventions représentent une part significative de leur travail et que la formation policière traditionnelle ne les prépare pas suffisamment pour intervenir adéquatement auprès de cette population. En réponse à ces considérations et dans l’objectif d’améliorer leur capacité d’agir, les forces policières se sont dotées de modèles de réponse policière spécialisée en intervention de crise. L’approche la plus répandue est l’équipe d’intervention de crise (« crisis intervention team » ou « CIT »), aussi appelée le modèle de Memphis. Il existe plusieurs variantes de ce modèle, mais les composantes principales, c’est-à-dire la formation avancée et la consolidation d’un partenariat avec le système de santé demeurent dans l’ensemble de ces structures. L’objectif de cette recherche consiste à sonder les perceptions des agents RIC, de leur partenaire fixe et des agents en attente de la formation afin de comprendre et de contraster leurs visions et leurs pratiques d’intervention en contexte de crise ou de santé mentale. Chaque groupe a apporté des précisions intéressantes. Nous avons conduit 12 entrevues qualitatives avec des policiers du SPVM. De façon générale, les participants rapportent que leurs pratiques d’intervention auprès des personnes en crise ou atteintes de troubles mentaux sont davantage ancrées dans une perspective de relation d’aide. Ils mentionnent également que la communication, l’écoute et la confiance doivent être privilégiées avant tout autre stratégie dans les situations qui les permettent et que la force doit être employée seulement lorsqu’elle est nécessaire, c’est-à-dire lorsque leur sécurité ou celle d’autrui est en péril ou lorsque la communication n’est pas possible. Puis, ils admettent que le recours à l’expertise des intervenants en santé mentale permet une analyse plus approfondie de la situation et de l’état mental de la personne visée par l’intervention. D’autre part, en ce qui concerne les limites de la formation policière traditionnelle, les candidats ont soulevé qu’il y a un manque de connaissances en matière de santé mentale ainsi qu’une difficulté associée à l’évaluation de l’état de la personne et du besoin de transport ont été soulevés. Sur le plan des apprentissages, les agents RIC disent avoir une compréhension plus globale de la problématique de santé mentale, de meilleures habiletés communicationnelles, une analyse plus approfondie de la situation, de plus grandes connaissances juridiques, une compréhension du fonctionnement des services hospitaliers ainsi qu’une appréciation particulière pour le partage de savoirs et les principes d’endiguement. Ils font part également de l’importance des rapports pour documenter l’évolution de l’état mental d’une personne et ils ajoutent que la dimension temporelle joue un rôle clé dans la résolution définitive de la problématique. Au sujet des partenaires, ils évoquent des retombées similaires. Toutefois, à la suite de la formation, ils reconnaissent davantage l’importance de leur rôle dans la sécurité de leur partenaire et ils y accordent dorénavant une attention marquée lors de ces interventions. Enfin, les agents non formés formulent des attentes relatives au développement d’outils et de compétences, ce qui leur sera rendu dans la formation RIC. Globalement, les agents RIC et les partenaires interviewés ont modifié leurs pratiques pour les arrimer avec la philosophie des interventions en contexte de crise ou de santé mentale. Ils ont également davantage confiance en leurs capacités et habiletés d’intervention auprès des personnes en crise ou atteintes de troubles mentaux grâce aux connaissances acquises dans la formation.